Multiple mechanisms, using various structures and having a range of response times, are employed to answer queries in communications networks. Domain Name System (DNS) is an example of such an existing mechanism for single-attribute queries (e.g., Internet Protocol (IP) address, mail server). DNS is a worldwide hierarchical distributed database that enables companies to be responsible of one or more database fragments. The distributed database supports the translation between a fully qualified domain name (FQDN) and an IP address.
DNS is often used in a naming service. A naming service provides mapping between a user identifier and the location of applications in the communications network. For example, Internet service providers (ISP) and Internet applications, such as Voice over Internet Protocol (VoIP) employ a naming service to convert a name into a physical address through a process referred to as naming resolution.
There are well-known mechanisms in Peer-to-peer (P2P) technology that are used to store address information such that end-users can retrieve it at a later time. P2P technology includes unstructured and structured P2P networks. An unstructured P2P network includes nodes that have limited or no knowledge of the information held by other peer nodes (peers). Typically, the unstructured P2P networks have an amorphous geometry, such as those used by Kazaa®, distributed by Sharman Networks Limited, and Skype®, distributed by Skype Limited Corporation, which provide an environment that is useful for highly volatile peers that continuously join and leave the P2P network.
Unlike DNS, which is a single-attribute query, many P2P networks allow users to place multi-attribute queries. That is, a user can ask for the entries that meet several criteria (e.g., age, gender, language, etc.). However, since the average peer lifetime is less than an hour, a limited amount of information can be stored in the peer nodes. In a P2P network, name to address translation is done cooperatively between peer nodes. The translation operation is sent to one or more node neighbors. In turn, the nodes will forward the query to neighbor nodes if it cannot perform the address translation.
In a structured P2P network, each node has a partial or total knowledge of the information held by other nodes. Typically, these networks form a geometric figure such as a tree, mesh, ring, or hypercube. Each peer has a routing table with the appropriate entries to exchange messages with its neighbors. The routing table enables the peer node to forward messages in the right direction. The routing table may be a distributed hash table (DHT), such as Chord and Pastry, which use a hashing function in every node. Each node is part of a ring and contains a routing table of other participating nodes. The size of the routing table is logbN, where N is the number of nodes in the network. Similarly, the number of (application-level) hops needed to find the appropriate node to answer a query is in average logbN.
Some P2P networks allow each node to store a routing table with N entries, one per node, which allows a one-hop solution to queries. This approach represents a fully connected graph at the application level. The one-hop structure is often used in low churn P2P networks, where peers remain in the network for long periods of time. Any update to the P2P network such a new node joining or a node leaving, modifies the routing table in every node. These updates are propagated using a two level hierarchy, where each node report changes to a slice leader. In turn, slice leaders periodically report changes to group leaders. These group leaders exchange update messages among themselves, and forward the new changes down to the slice leaders, who will forward them to individual nodes. The slice leaders and the group leaders are both peers and are configured to select a new leader in case a leader is saturated or dies.
DNS and P2P, therefore, provide mechanisms for responding to queries such as those queries used in a naming service. The caching scheme in DNS, however, has a limited or no reactive mechanism to update the different caches. As such, some query responses return stale information. Stale information is of particularly importance for mobile users where IP addresses can change at relatively short intervals.
Additionally, the average DNS response time varies from one geographic region to the next since most DNS servers are concentrated in one region, i.e., United States. The 98-percentile response time can vary from 0.05 seconds to 11 seconds due to various considerations including: server concentration in one geographic region, DNS server overload, ill-configured DNS servers, long timeout periods and hierarchical lookup starting from root servers. Range query requests and multi-attribute queries are also not supported in DNS.
As noted above, unstructured P2P networks include no or limited knowledge of information stored at a neighboring node. Thus, a user requests has to be propagated exponentially through out the network. Further, an imprecise answer can be returned to the sender, since a query of all the nodes is not assured. Thus, the information can be stored one or more hops away from any of the visited nodes.
Though many mechanisms exist for responding to queries, improvements in the art would prove beneficial.